package q745_WordFilter;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WordFilter {

    /*
        维护两棵字典树，一棵正插，一棵倒插
        由于某个前缀 或 后缀会进行多次查询，因此使用 map 缓存起来
    */
    Trie prefixTree;
    Trie suffixTree;
    Map<String, List<Integer>> prefixMap;
    Map<String, List<Integer>> suffixMap;
    public WordFilter(String[] words) {
        prefixTree = new Trie();
        suffixTree = new Trie();
        prefixMap = new HashMap<>();
        suffixMap = new HashMap<>();

        for(int i = 0; i < words.length; i++){
            prefixTree.insert(words[i], i);
            //翻转字符串
            String reverseStr = new StringBuilder(words[i]).reverse().toString();
            suffixTree.insert(reverseStr, i);
        }
    }

    public int f(String prefix, String suffix) {
        suffix = new StringBuilder(suffix).reverse().toString();

        List<Integer> prefixList;
        List<Integer> suffixList;

        // 获取满足前缀的字符串列表
        if(prefixMap.containsKey(prefix)){
            prefixList = prefixMap.get(prefix);
        }else{
            prefixList = prefixTree.search(prefix);
            prefixMap.put(prefix, prefixList);
        }
        // 获取满足后缀的字符串列表
        if(suffixMap.containsKey(suffix)){
            suffixList = suffixMap.get(suffix);
        }else{
            suffixList = suffixTree.search(suffix);
            suffixMap.put(suffix, suffixList);
        }

        /*
        由于找权重最大的，即索引最大的，因此对两个列表进行倒序遍历
        如果
        pre[i] == suff[j]，那么答案即为 pre[i] 或 suff[j]
        pre[i] > suff[j]，表示 pre[i] 过大，需要缩小，因此 i--
        pre[i] < suff[j]，表示 suff[i] 过大，需要缩小，因此 j--
        */
        int len1 = prefixList.size();
        int len2 = suffixList.size();
        if(len1 == 0 || len2 == 0){
            return -1;
        }
        int i = len1 - 1;
        int j = len2 - 1;
        while(i >= 0 && j >= 0){
            int diff = prefixList.get(i) - suffixList.get(j);
            if(diff == 0){
                return prefixList.get(i);
            }else if(diff > 0){
                i--;
            }else{
                j--;
            }
        }
        return -1;
    }

    class TrieNode{
        List<Integer> vals;
        TrieNode[] childern;
        //记录当前节点是否是某个单词的结尾
        public TrieNode() {
            vals = new ArrayList<>();
            childern = new TrieNode[26];
        }
    }

    class Trie {

        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word, int index) {
            TrieNode cur = root;
            //注意：这里添加表示前缀或后缀为 ""
            cur.vals.add(index);
            for(int i = 0; i < word.length(); i++){
                int ch = word.charAt(i) - 'a';
                if(cur.childern[ch] == null){
                    cur.childern[ch] = new TrieNode();
                }
                cur = cur.childern[ch];
                cur.vals.add(index);
            }
        }

        public List<Integer> search(String word){
            TrieNode cur = root;
            for(char ch : word.toCharArray()){
                int num = ch - 'a';
                if(cur.childern[num] == null){
                    return new ArrayList<>();
                }
                cur = cur.childern[num];
            }
            return cur.vals;
        }
    }
}

